package com.stu.collection;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * HashMap和HashSet详细演示
 * 涵盖：
 * - HashMap底层原理（数组+链表+红黑树）
 * - 哈希冲突处理机制
 * - 扩容机制详解
 * - HashSet实现原理
 * - HashMap线程安全问题
 * - JDK1.7和JDK1.8的区别
 * 
 * @author 学习者
 * @version 1.0
 */
public class HashMapAndHashSet {
    
    public static void main(String[] args) {
        System.out.println("=== HashMap和HashSet详细演示 ===");
        
        // 1. HashMap基本使用和原理
        demonstrateHashMapBasics();
        
        // 2. 哈希冲突演示
        demonstrateHashCollision();
        
        // 3. HashMap扩容机制
        demonstrateResizing();
        
        // 4. HashSet原理演示
        demonstrateHashSet();
        
        // 5. HashMap线程安全问题
        demonstrateThreadSafety();
        
        // 6. JDK版本差异
        demonstrateJDKDifferences();
        
        // 7. 性能优化建议
        performanceOptimization();
    }
    
    /**
     * HashMap基本使用和底层原理演示
     */
    private static void demonstrateHashMapBasics() {
        System.out.println("\n=== HashMap基本原理演示 ===");
        
        // 创建HashMap
        HashMap<String, Integer> map = new HashMap<>();
        
        System.out.println("\nHashMap底层结构：");
        System.out.println("1. JDK1.8之前：数组 + 链表");
        System.out.println("2. JDK1.8之后：数组 + 链表 + 红黑树");
        System.out.println("3. 默认初始容量：16（2的4次方）");
        System.out.println("4. 默认负载因子：0.75");
        System.out.println("5. 树化阈值：链表长度 >= 8且数组长度 >= 64");
        System.out.println("6. 反树化阈值：红黑树节点 <= 6");
        
        // 添加元素演示
        System.out.println("\n添加元素过程演示：");
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 15);
        map.put("grape", 25);
        
        System.out.println("当前map内容：" + map);
        
        // 演示key的hashCode计算
        System.out.println("\nkey的hash值计算过程：");
        String key = "apple";
        int hashCode = key.hashCode();
        int hash = hashCode ^ (hashCode >>> 16); // HashMap中的hash函数
        System.out.println("key: " + key);
        System.out.println("hashCode: " + hashCode + " (二进制: " + Integer.toBinaryString(hashCode) + ")");
        System.out.println("hash: " + hash + " (二进制: " + Integer.toBinaryString(hash) + ")");
        
        // 演示数组索引计算
        int capacity = 16; // 假设当前容量为16
        int index = hash & (capacity - 1); // 等价于 hash % capacity，但位运算更快
        System.out.println("数组索引: " + index + " (hash & " + (capacity-1) + ")");
        
        System.out.println("\nHashMap存储过程：");
        System.out.println("1. 计算key的hash值：hash = key.hashCode() ^ (key.hashCode() >>> 16)");
        System.out.println("2. 计算数组索引：index = hash & (capacity - 1)");
        System.out.println("3. 如果该位置为空，直接存储");
        System.out.println("4. 如果该位置有元素，比较hash和key");
        System.out.println("5. 如果key相同，替换value");
        System.out.println("6. 如果key不同，形成链表或红黑树");
        
        // 演示get操作
        System.out.println("\n查找元素过程：");
        Integer value = map.get("apple");
        System.out.println("map.get(\"apple\") = " + value);
        System.out.println("查找过程：");
        System.out.println("1. 计算\"apple\"的hash值和数组索引");
        System.out.println("2. 在对应位置查找");
        System.out.println("3. 如果是链表，遍历比较key");
        System.out.println("4. 如果是红黑树，按树结构查找");
        
        // 演示null值处理
        System.out.println("\nnull值处理：");
        map.put(null, 100);
        map.put("nullValue", null);
        System.out.println("map.put(null, 100): " + map.get(null));
        System.out.println("map.put(\"nullValue\", null): " + map.get("nullValue"));
        System.out.println("HashMap允许一个null键和多个null值");
        System.out.println("null键总是存储在数组的第0个位置");
    }
    
    /**
     * 哈希冲突演示
     */
    private static void demonstrateHashCollision() {
        System.out.println("\n=== 哈希冲突演示 ===");
        
        System.out.println("\n什么是哈希冲突？");
        System.out.println("不同的key计算出相同的数组索引，就发生了哈希冲突");
        
        // 创建自定义类演示哈希冲突
        HashMap<HashCollisionDemo, String> collisionMap = new HashMap<>();
        
        // 创建具有相同hash值的对象
        HashCollisionDemo obj1 = new HashCollisionDemo("A", 1);
        HashCollisionDemo obj2 = new HashCollisionDemo("B", 1); // 相同hash值
        HashCollisionDemo obj3 = new HashCollisionDemo("C", 1); // 相同hash值
        
        collisionMap.put(obj1, "值1");
        collisionMap.put(obj2, "值2");
        collisionMap.put(obj3, "值3");
        
        System.out.println("\n哈希冲突示例：");
        System.out.println("obj1.hashCode() = " + obj1.hashCode());
        System.out.println("obj2.hashCode() = " + obj2.hashCode());
        System.out.println("obj3.hashCode() = " + obj3.hashCode());
        System.out.println("三个对象的hash值相同，会存储在同一个数组位置");
        
        System.out.println("\n冲突解决方案：");
        System.out.println("1. JDK1.8之前：链表法");
        System.out.println("   - 相同索引的元素形成单向链表");
        System.out.println("   - 新元素插入到链表头部（头插法）");
        System.out.println("   - 查找时需要遍历整个链表");
        
        System.out.println("\n2. JDK1.8之后：链表 + 红黑树");
        System.out.println("   - 链表长度 <= 8：使用链表");
        System.out.println("   - 链表长度 > 8 且数组长度 >= 64：转换为红黑树");
        System.out.println("   - 红黑树节点 <= 6：退化为链表");
        System.out.println("   - 新元素插入到链表尾部（尾插法）");
        
        // 演示链表转红黑树的条件
        System.out.println("\n链表转红黑树的条件：");
        System.out.println("static final int TREEIFY_THRESHOLD = 8;     // 树化阈值");
        System.out.println("static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量");
        System.out.println("static final int UNTREEIFY_THRESHOLD = 6;   // 反树化阈值");
        
        System.out.println("\n为什么选择8作为树化阈值？");
        System.out.println("1. 泊松分布计算：链表长度为8的概率约为0.00000006");
        System.out.println("2. 红黑树的查找时间复杂度为O(log n)");
        System.out.println("3. 当链表长度为8时，查找性能已经很差");
        System.out.println("4. 红黑树虽然查找快，但占用内存更多");
    }
    
    /**
     * HashMap扩容机制演示
     */
    private static void demonstrateResizing() {
        System.out.println("\n=== HashMap扩容机制演示 ===");
        
        System.out.println("\n扩容触发条件：");
        System.out.println("当前元素数量 > 容量 * 负载因子（默认0.75）");
        
        // 创建小容量的HashMap演示扩容
        HashMap<Integer, String> map = new HashMap<>(4, 0.75f);
        
        System.out.println("\n初始容量：4，负载因子：0.75");
        System.out.println("扩容阈值：4 * 0.75 = 3");
        
        // 添加元素观察扩容
        for (int i = 1; i <= 6; i++) {
            map.put(i, "值" + i);
            System.out.println("添加第" + i + "个元素，当前大小：" + map.size());
            if (i == 3) {
                System.out.println("  -> 达到扩容阈值，即将扩容");
            }
            if (i == 4) {
                System.out.println("  -> 扩容完成，新容量：8，新阈值：6");
            }
        }
        
        System.out.println("\n扩容过程详解：");
        System.out.println("1. 创建新数组，容量为原来的2倍");
        System.out.println("2. 重新计算所有元素的位置（rehash）");
        System.out.println("3. 将元素迁移到新数组");
        System.out.println("4. 更新阈值：新容量 * 负载因子");
        
        System.out.println("\nJDK1.8扩容优化：");
        System.out.println("1. 元素位置计算优化：");
        System.out.println("   - 原位置：hash & (oldCap - 1)");
        System.out.println("   - 新位置：hash & (newCap - 1)");
        System.out.println("   - 由于newCap = oldCap * 2，新位置只有两种可能：");
        System.out.println("     * 原位置：hash & oldCap == 0");
        System.out.println("     * 原位置 + oldCap：hash & oldCap != 0");
        
        System.out.println("\n2. 链表拆分优化：");
        System.out.println("   - 将原链表拆分为两个链表");
        System.out.println("   - 保持原有顺序，避免死循环");
        System.out.println("   - 使用loHead/loTail和hiHead/hiTail分别维护两个链表");
        
        System.out.println("\n负载因子选择0.75的原因：");
        System.out.println("1. 时间和空间的权衡");
        System.out.println("2. 负载因子过小：浪费空间，但冲突少");
        System.out.println("3. 负载因子过大：节省空间，但冲突多");
        System.out.println("4. 0.75是经过大量测试的最优值");
    }
    
    /**
     * HashSet原理演示
     */
    private static void demonstrateHashSet() {
        System.out.println("\n=== HashSet原理演示 ===");
        
        System.out.println("\nHashSet底层实现：");
        System.out.println("HashSet内部使用HashMap实现");
        System.out.println("元素作为HashMap的key，value是固定的PRESENT对象");
        
        // HashSet基本使用
        HashSet<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("apple"); // 重复元素不会被添加
        
        System.out.println("\nHashSet内容：" + set);
        System.out.println("大小：" + set.size());
        
        // 演示HashSet的实现原理
        System.out.println("\nHashSet源码分析：");
        System.out.println("private transient HashMap<E,Object> map;");
        System.out.println("private static final Object PRESENT = new Object();");
        System.out.println("");
        System.out.println("public boolean add(E e) {");
        System.out.println("    return map.put(e, PRESENT) == null;");
        System.out.println("}");
        System.out.println("");
        System.out.println("public boolean contains(Object o) {");
        System.out.println("    return map.containsKey(o);");
        System.out.println("}");
        
        // 演示HashSet的特性
        System.out.println("\nHashSet特性：");
        System.out.println("1. 无序：不保证元素的顺序");
        System.out.println("2. 唯一：不允许重复元素");
        System.out.println("3. 允许null：最多一个null元素");
        System.out.println("4. 非线程安全");
        
        // 添加null演示
        set.add(null);
        System.out.println("添加null后：" + set);
        
        // 演示equals和hashCode的重要性
        System.out.println("\nequals和hashCode的重要性：");
        HashSet<Person> personSet = new HashSet<>();
        Person p1 = new Person("张三", 25);
        Person p2 = new Person("张三", 25); // 内容相同但是不同对象
        
        personSet.add(p1);
        personSet.add(p2);
        
        System.out.println("Person集合大小：" + personSet.size());
        System.out.println("Person集合内容：" + personSet);
        System.out.println("说明：Person类正确重写了equals和hashCode方法");
        
        // LinkedHashSet演示
        System.out.println("\nLinkedHashSet演示：");
        LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("third");
        linkedSet.add("first");
        linkedSet.add("second");
        
        System.out.println("LinkedHashSet：" + linkedSet);
        System.out.println("特点：保持插入顺序，底层使用HashMap + 双向链表");
        
        // TreeSet演示
        System.out.println("\nTreeSet演示：");
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("zebra");
        treeSet.add("apple");
        treeSet.add("banana");
        
        System.out.println("TreeSet：" + treeSet);
        System.out.println("特点：自动排序，底层使用红黑树，元素必须实现Comparable或提供Comparator");
    }
    
    /**
     * HashMap线程安全问题演示
     */
    private static void demonstrateThreadSafety() {
        System.out.println("\n=== HashMap线程安全问题演示 ===");
        
        System.out.println("\nHashMap线程安全问题：");
        System.out.println("1. 数据丢失：多线程同时put可能导致数据覆盖");
        System.out.println("2. 死循环：JDK1.7中扩容时可能形成环形链表");
        System.out.println("3. 数据不一致：读写并发可能读到不完整的数据");
        
        // 演示数据丢失问题（简化演示）
        System.out.println("\n数据丢失问题演示：");
        HashMap<Integer, Integer> unsafeMap = new HashMap<>();
        
        // 模拟并发put操作可能的问题
        System.out.println("假设两个线程同时执行put操作：");
        System.out.println("线程1：map.put(1, 100)");
        System.out.println("线程2：map.put(2, 200)");
        System.out.println("可能的问题：");
        System.out.println("1. 两个线程同时计算到相同的数组位置");
        System.out.println("2. 线程1创建节点并准备插入");
        System.out.println("3. 线程2也创建节点并插入，覆盖了线程1的操作");
        System.out.println("4. 结果：线程1的数据丢失");
        
        // JDK1.7死循环问题
        System.out.println("\nJDK1.7死循环问题：");
        System.out.println("扩容时使用头插法重建链表，多线程环境下可能形成环形链表");
        System.out.println("导致get操作时无限循环，CPU使用率100%");
        
        System.out.println("\n线程安全解决方案：");
        
        // 1. Hashtable
        System.out.println("\n1. 使用Hashtable：");
        Hashtable<String, String> hashtable = new Hashtable<>();
        hashtable.put("key1", "value1");
        System.out.println("特点：方法级别synchronized，性能较差");
        
        // 2. Collections.synchronizedMap
        System.out.println("\n2. 使用Collections.synchronizedMap：");
        Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());
        syncMap.put("key2", "value2");
        System.out.println("特点：包装器模式，每个方法都加锁");
        
        // 3. ConcurrentHashMap
        System.out.println("\n3. 使用ConcurrentHashMap（推荐）：");
        ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
        concurrentMap.put("key3", "value3");
        System.out.println("特点：分段锁（JDK1.7）或CAS+synchronized（JDK1.8），性能最好");
        
        System.out.println("\nConcurrentHashMap原理：");
        System.out.println("JDK1.7：分段锁（Segment），每个Segment是一个小的HashMap");
        System.out.println("JDK1.8：CAS + synchronized，只锁定数组的某个位置");
        System.out.println("优点：读操作几乎无锁，写操作锁粒度小，性能优秀");
    }
    
    /**
     * JDK版本差异演示
     */
    private static void demonstrateJDKDifferences() {
        System.out.println("\n=== JDK版本差异演示 ===");
        
        System.out.println("\nJDK1.7 vs JDK1.8 HashMap差异：");
        
        System.out.println("\n1. 数据结构：");
        System.out.println("JDK1.7：数组 + 链表");
        System.out.println("JDK1.8：数组 + 链表 + 红黑树");
        
        System.out.println("\n2. 插入方式：");
        System.out.println("JDK1.7：头插法（新元素插入链表头部）");
        System.out.println("JDK1.8：尾插法（新元素插入链表尾部）");
        
        System.out.println("\n3. 扩容机制：");
        System.out.println("JDK1.7：重新计算所有元素的hash值和位置");
        System.out.println("JDK1.8：优化算法，元素位置只有两种可能");
        
        System.out.println("\n4. hash函数：");
        System.out.println("JDK1.7：多次位运算");
        System.out.println("JDK1.8：简化为 hash = key.hashCode() ^ (key.hashCode() >>> 16)");
        
        System.out.println("\n5. 线程安全：");
        System.out.println("JDK1.7：扩容时可能形成环形链表，导致死循环");
        System.out.println("JDK1.8：改为尾插法，避免了死循环问题");
        
        System.out.println("\n6. 性能优化：");
        System.out.println("JDK1.7：链表过长时查找性能O(n)");
        System.out.println("JDK1.8：红黑树优化，最坏情况查找性能O(log n)");
        
        System.out.println("\n为什么JDK1.8要改为尾插法？");
        System.out.println("1. 避免扩容时的死循环问题");
        System.out.println("2. 保持元素的相对顺序");
        System.out.println("3. 便于链表转红黑树的操作");
        
        System.out.println("\n红黑树的优势：");
        System.out.println("1. 平衡二叉树，查找效率稳定");
        System.out.println("2. 最坏情况下查找时间复杂度O(log n)");
        System.out.println("3. 插入删除操作也是O(log n)");
        System.out.println("4. 相比AVL树，插入删除时旋转次数更少");
    }
    
    /**
     * 性能优化建议
     */
    private static void performanceOptimization() {
        System.out.println("\n=== HashMap性能优化建议 ===");
        
        System.out.println("\n1. 合理设置初始容量：");
        System.out.println("如果知道大概的元素数量，建议设置合适的初始容量");
        System.out.println("初始容量 = 预期元素数量 / 负载因子 + 1");
        
        // 演示初始容量设置
        int expectedSize = 1000;
        int initialCapacity = (int) (expectedSize / 0.75f) + 1;
        HashMap<Integer, String> optimizedMap = new HashMap<>(initialCapacity);
        System.out.println("预期1000个元素，建议初始容量：" + initialCapacity);
        
        System.out.println("\n2. 选择合适的负载因子：");
        System.out.println("默认0.75是最优选择，一般不建议修改");
        System.out.println("负载因子过小：浪费内存");
        System.out.println("负载因子过大：增加冲突，降低性能");
        
        System.out.println("\n3. 重写equals和hashCode：");
        System.out.println("确保自定义类正确重写equals和hashCode方法");
        System.out.println("hashCode分布要均匀，避免大量冲突");
        System.out.println("equals和hashCode要保持一致性");
        
        System.out.println("\n4. 避免频繁扩容：");
        System.out.println("扩容是昂贵的操作，需要重新计算所有元素位置");
        System.out.println("合理预估容量可以减少扩容次数");
        
        System.out.println("\n5. 选择合适的Map实现：");
        System.out.println("HashMap：一般场景，性能最好");
        System.out.println("LinkedHashMap：需要保持插入顺序");
        System.out.println("TreeMap：需要排序");
        System.out.println("ConcurrentHashMap：多线程环境");
        
        System.out.println("\n6. 注意内存泄漏：");
        System.out.println("及时移除不需要的元素");
        System.out.println("注意key对象的生命周期");
        System.out.println("避免使用可变对象作为key");
        
        System.out.println("\n7. 遍历优化：");
        System.out.println("使用entrySet()而不是keySet()进行遍历");
        System.out.println("避免在遍历过程中修改Map结构");
        
        // 演示高效遍历
        HashMap<String, Integer> map = new HashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        
        System.out.println("\n高效遍历方式：");
        System.out.println("// 推荐：使用entrySet");
        System.out.println("for (Map.Entry<String, Integer> entry : map.entrySet()) {");
        System.out.println("    String key = entry.getKey();");
        System.out.println("    Integer value = entry.getValue();");
        System.out.println("}");
        
        System.out.println("\n// 不推荐：使用keySet");
        System.out.println("for (String key : map.keySet()) {");
        System.out.println("    Integer value = map.get(key); // 额外的查找操作");
        System.out.println("}");
    }
}

/**
 * 用于演示哈希冲突的类
 */
class HashCollisionDemo {
    private String name;
    private int value;
    
    public HashCollisionDemo(String name, int value) {
        this.name = name;
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        // 故意返回相同的hash值来演示冲突
        return value;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        HashCollisionDemo that = (HashCollisionDemo) obj;
        return value == that.value && Objects.equals(name, that.name);
    }
    
    @Override
    public String toString() {
        return name + "(" + value + ")";
    }
}

/**
 * 正确实现equals和hashCode的Person类
 */
class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}